package com.cet.algorithm.回溯.分割回文串;

import java.util.*;

/**
 * @program: cet-practice
 * @description: 分割回文串
 * @author: 陈恩涛
 * @create: 2023-05-30 17:06
 **/
public class LC131 {

    // 返回结果集
    List<List<String>> result = new LinkedList<>();

    // 存放一种切分的结果集
    LinkedList<String> path = new LinkedList<>();

    /**
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串
     */
    public List<List<String>> partition(String s) {

        backTracing(s, 0);
        return result;
    }

    public void backTracing(String s, int startIdx) {

        // 递归终止条件
        if (startIdx >= s.length()) {
            result.add(new LinkedList<>(path));
        }

        //单层递归逻辑
        for (int i = startIdx; i < s.length(); i++) {
            String subString = s.substring(startIdx, i + 1);
            if (!isPalindromeString(subString)) {
                continue;
            }
            path.add(subString);
            backTracing(s, i + 1);
            path.removeLast();
        }
    }

    // 字符串是否为回文串的字典
    Map<String, Boolean> palindromesMap = new HashMap<>();

    /**
     * 判断字符串是否问回文串
     * @param s 带判断字符串
     * @return 是否为回文串
     */
    public boolean isPalindromeString(String s) {

        Optional<Boolean> optional = Optional.ofNullable(palindromesMap.get(s));

        if (optional.isPresent()) {
            return optional.get();
        }

        for (int left = 0, right = s.length() - 1; left < right; left++, right--) {
            if (s.charAt(left) != s.charAt(right)) {
                palindromesMap.put(s, false);
                return false;
            }
        }
        palindromesMap.put(s, true);
        return true;
    }

    public static void main(String[] args) {
        LC131 lc131 = new LC131();
        System.out.println(lc131.partition("abba"));
    }

}
